Abstract: This paper discusses the principles of connectivity, similarity and comparability in image identification based on the mixed-graph structure. It proposes a reduction algorithm that compares each composite node in a mixed-graph against a reference image to find the possible matches and the corresponding maximal similarity value (i.e., compound similarity), and reduces the mixed-graph using the best matches. To ease the calculation and better illustrate the reduction process, this paper labels the nodes in the mixed-graph with single attributes, and simplifies the similarity computation to sort and query operations with a linear complexity. The results show that the method is efficient and feasible.


Key words: mixed-graph, connectivity, similarity, comparability, mixed-graph structure reduction, region merging, matching algorithm, compound similarity